1. Field of the Invention
The present invention relates to a hybrid channel assignment method and a router thereof in Wireless Local Area Network (WLAN) mesh networks. More particularly, the invention relates to a hybrid channel assignment method and a router thereof, which can assign channels by centralized processing, and in the case of reallocable links, reassigning the assigned channels based upon dynamically-changing traffic characteristics.
2. Description of the Related Art
Conventional channel assignment methods used in WLAN mesh networks generally include centralized channel assignment and distributed channel assignment.
In the centralized channel assignment, a server collects information about all nodes, links and traffic characteristics, and based upon the collected information, selects channels to assign. In the distributed channel assignment method, a node selects a channel to use based upon its own information and information acquired from neighbor nodes.
Representative algorithms of the centralized channel assignment include “Centralized Channel Assignment and Routing Algorithms for Multi-channel Wireless Mesh Networks” proposed in ACM Mobile Computing and Communications Review (MC2R), Vol. 8, No. 2, April, 2004, and “Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks” published in MobiHoc, 2005.
Both examples of the centralized channel assignment method include routers of the network and a channel assignment server. The channel assignment server may also function as a router, or may be provided separately from the router. FIGS. 1A to 1C illustrate a channel assignment process according to the centralized channel assignment.
FIG. 1A is a network topology prior to new channel assignment according to the centralized channel assignment.
As shown in FIG. 1A, the network includes a channel assignment server 110 and routers 120 to 160. The channel assignment server can also act as a router as mentioned above. In FIG. 1A, it is assumed that the channel assignment server 110 also acts as a router unless otherwise disclosed.
Respective routers 120 to 160 transmit traffic information necessary for channel calculation to the channel assignment server 110.
The channel assignment server 110 checks whether or not new channel assignment is necessary by referring to traffic information and so on, which is received from the respective routers 120 to 160.
If a new channel assignment is not necessary, the channel assignment server 110 does not perform channel assignment. If a new channel assignment is necessary, the server 110 searches for channels to be newly used via calculation. In this case, information on the channels to be newly used is transmitted, on a channel assignment request message, to the respective routers 120 to 160.
Describing the dotted parts of FIG. 1A in more detail, each of the routers 120 to 160 transmits traffic information to the channel assignment server 110.
Upon receiving the traffic information, the channel assignment server 110 assigns Channel 1, Channel 3, Channel 1, Channel 2 and Channel 1, respectively, to the router 120, the router 130, the router 140, the router 150 and the router 160.
FIG. 1B is a network topology during new channel assignment according to the centralized channel assignment.
Referring to FIG. 1B, it is assumed that new channel assignment is necessary due to decreased traffic between the router 120 and the router 150 and increased traffic between the router 140 and the router 150.
If traffic characteristics are greatly changed after the channel assignment, the channel assignment server 110 calculates channels to be newly used, and transmits information on the channels to be newly used to routers that require channel switching.
The traffic flow of FIG. 1B is changed from that of the previous channel assigned state. Here, based upon the traffic information, which is received in FIG. 1A, the channel assignment server 110 determines whether or not new channel assignment is necessary. If a new channel assignment is necessary, the channel assignment server 110 searches for the channels to be used via calculation. In FIG. 1B, it is required to reestablish the channels of the router 120, the router 140 and the router 150.
In this case, the channel assignment server 110 transmits a channel assignment request message to the routers 120, 140 and 150. The channel assignment request message includes information on the channels, which are selected to be newly used. This procedure is illustrated with dotted lines in FIG. 1B.
In this case, however, the channel of the routers 130 and 160 is not reestablished since the traffic flow between the routers 130 and 160 is not changed. Thus, the channel assignment server 110 does not transmit the channel assignment request message to the routers 130 and 160.
FIG. 1C is a network topology after new channel assignment according to the centralized channel assignment.
The channel assignment is finished when respective routers establish a new channel in response to the channel assignment request message. When the channel assignment request message is received along the paths as shown in FIG. 1B, the routers 120, 140 and 150 change the channels with reference to channel information in the channel assignment request message, the channel information describing the channels to be newly used. Referring to FIG. 1C, Channel 2 between the router 120 and the router 150 is terminated, and new Channel 2 is established between the router 140 and the router 150. This is because the channel assignment is made based upon the fact that the traffic between the router 120 and the router 150 decreases and the traffic between the router 140 and the router 150 increases.
According to the centralized channel assignment as described above, network performance can be enhanced. However, the centralized channel assignment requires a long process time since channel assignment is always carried out for the entire network. Due to the long process time, traffic packets may be lost or sessions may be frequently broken. In order to prevent these problems, the centralized channel assignment does not frequently assign channels. In this case, however, channels cannot be consistent with dynamically changing traffic, and thus network performance degrades.
As a representative algorithm of the distributed channel assignment, “Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network” was published by Infocom, 2005. This algorithm uses the distributed channel assignment instead of the centralized channel assignment.
Unlike the centralized channel assignment, a network of the distributed channel assignment includes only routers without a channel assignment server. FIGS. 2A to 2C illustrates a channel assignment process according to the distributed channel assignment.
FIG. 2A is a network topology before new channel assignment according to the distributed channel assignment.
According to the distributed channel assignment, there are no channel assignment servers, and the routers also act as a channel assignment server.
Each of the routers receives traffic information from other routers, which are connected to a gateway therethrough. In this case, those routers, which transmit the traffic information, are referred to as lower level routers, and those routers, which receive the traffic information, are referred to as higher level routers. In FIG. 2A, router 210 acts as an higher level router, and routers 211 to 215, 220, 230, 240, 250, 260 and 270 act as lower level routers.
All the lower level routers are not required to transmit their own traffic information to the higher level router. That is, some of the lower level routers present in a predetermined depth transmit traffic information to the higher level router. Here, the predetermined depth corresponds to a circled area in FIG. 2A. Therefore, as designated with dotted lines, only the routers 211 to 215 transmit traffic information to the router 210, which acts as the higher level router.
The higher level router can balance traffic of the lower level routers directly connected thereto, by instructing the next lower level routers, which are in a lower level than the lower level routers directly connected to the higher level router, to connect to other lower level routers.
In the same method, all the routers perform channel assignments to their own lower level routers using information from the lower level routers.
For example, the router 210 of FIG. 2A receives traffic information from the routers 211 to 215, which are in the predetermined depth, and monitors whether or not traffic is balanced. In the same fashion, other higher level routers in the network can receive traffic from their own lower level routers and monitors the received traffic.
FIG. 2B is a network topology during new channel assignment according to the distributed channel assignment.
It is assumed that the traffic flow is changed from that shown in FIG. 2A, so that more amount of traffic is conveyed at the link between router 210 and router 211 than at the link between router 210 and router 212. In this case, router 210 instructs router 214 to connect as a lower level router of router 212 in order to balance the amount of traffic.
Specifically, router 210 sends a channel assignment request message to routers 211, 212 and 214, the channel assignment request message including information on the channels to be newly assigned. In FIG. 2B, this procedure is indicated with dotted lines. Then, a channel assignment will be made to disable the channel assigned to the link between router 211 and router 214, that is, a lower level router of router 211, thereby reducing the amount of traffic conveyed toward router 211.
FIG. 2C is a network topology after the new channel assignment according to the distributed channel assignment.
When the channel assignment request message is received, the lower level routers complete the channel assignment. Referring to FIG. 2C, Channel 2 assigned to the link between routers 211 and 214 is disabled, and Channel 3 is newly assigned to the link between routers 212 and 214.
Then, traffic is transmitted through the newly assigned channels in the network.
In the distributed channel assignment, less packets are lost and less sessions are broken in the transmission traffic as compared to the centralized channel assignment. This is because the channel assignment is performed by each node. However, since entire network information is not used to assign channels, the performance of the distributed assignment is inferior to that of the centralized channel assignment.
In the case of the centralized channel assignment, channel assignment consistent with the actual network situation is impossible owing to a long update cycle. In the centralized channel assignment, when the channel assignment server is in trouble, the entire network loses its functionality. In the case of assigning channels by the distributed channel assignment, channel assignment may be incorrect since it is performed without information on the entire network.